// https://leetcode.cn/problems/three-steps-problem-lcci/

// 算法思路总结：
// 1. 动态规划求解三步爬楼梯问题
// 2. 状态定义：dp[i]表示到达第i阶的方法数
// 3. 状态转移：dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
// 4. 模运算防止中间结果溢出
// 5. 时间复杂度：O(n)，空间复杂度：O(n)

#include <iostream>
using namespace std;

#include <vector>

class Solution 
{
public:
    const int mod = 1000000007;
    int waysToStep(int n) 
    {
        vector<long long> dp(n + 1);
        if (n == 1) return 1;
        if (n == 2) return 2;

        dp[0] = 1, dp[1] = 1, dp[2] = 2;

        for (int i = 3 ; i <= n ; i++)
            dp[i] = (dp[i - 1] + dp[i - 2] + dp[i - 3]) % mod;

        return dp[n];
    } 
};

int main()
{
    int n1 = 3, n2 = 5;
    Solution sol;

    cout << sol.waysToStep(n1) << endl;
    cout << sol.waysToStep(n2) << endl;

    return 0;
}